package 面试.同城;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author : K k
 * @date : 21:09 2020/10/11
 */
public class 同城_2 {
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();

    public ArrayList<ArrayList<Integer>> binaryTreeScan (int[] input) {
        ArrayList<Integer> ans=new ArrayList<>();
        Deque<Integer> path=new LinkedList<>();
        int index=0;
        path.push(input[0]);
        //前序
        while(!path.isEmpty()){
            Integer root = path.removeLast();
            ans.add(root);
            if (index+2<input.length){
                if (input[index+2]!=-1){
                    path.addLast(input[index+2]);
                }
            }
            if (index+1<input.length){
                if (input[index+1]!=-1) {
                    path.addLast(input[index + 1]);
                }
            }
            index=index+2;
        }
        res.add(ans);
        return res;
    }

    public static void main(String[] args) {
        同城_2 x=new 同城_2();
        System.out.println(x.binaryTreeScan(new int[]{1, 7, 2, 6, -1, 4, 8}));
        //176248
    }
}
